Date: Tue, 26 Nov 1996 18:49:54 GMT
Server: NCSA/1.4.1
Content-type: text/html
Last-modified: Tue, 19 Nov 1996 18:14:11 GMT
Content-length: 1753

<HEAD>
<TITLE>Syllabus</TITLE>
</HEAD>
<BODY>
<P>
<H3> <b>Randomized Algorithms</b></H3>

<P>
<P>
<b>Instructor</b>.  Richard Cole, WWW412, tel: 998-3119, cole@cs.nyu.edu.
<P>

<b>Syllabus</b>.
Randomization is a powerful tool for achieving efficiency and/or
simplicity in many settings.
This course will study a variety of techniques for using
randomization in algorithm design.
Randomization typically introduces uncertainty, which could
be uncertainty regarding the result, or uncertainty regarding the
algorithm's performance; but this is tolerable if it is of
sufficiently low probability.
Primality testing and quicksort, respectively,
provide examples of each of these.
Techniques for analyzing the (probabilistic) correctness and
performance of randomized algorithms will be a central
part of the course.

<p>
<b>Prerequisites</b>.
Honors Analysis of Algorithms, or A in Fundamental Algorithms,
or equivalent background with permission of the instructor.
The course also assumes familiarity with basic probability and
counting, such as might be encoutered in an analysis of quicksort
or of an idealized hashing scheme.

<p>
<b>Assignments</b>.
There will be homeworks comprising
problems drawn from the textbook and elsewhere.
Late homeworks will not be accepted (except in the event of
illness of other unavoidable circumstances).
If for some reason you will be unable to hand in a homework on time,
please discuss it with me beforehand.

<p>
<b>Required text</b>.
Motwani and Raghavan, Randomized Algorithms.

<p>
<p>
<p>
<!WA0><a href="http://cs.nyu.edu/">CS Department</a>,
<!WA1><a href="http://www.nyu.edu/">NYU</a>
<p>
<font=-1>
<!WA2><a href=mailto:cole@cs.nyu.edu>cole@cs.nyu.edu</a> (Richard Cole)<br>
Last modified: Nov 11, 1996</I>
</ADDRESS>
</BODY>
